Search Results

Documents authored by Yang, Everett


Document
Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs

Authors: Sariel Har-Peled and Everett Yang

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
We present a (1-ε)-approximation algorithms for maximum cardinality matchings in disk intersection graphs - all with near linear running time. We also present an estimation algorithm that returns (1±ε)-approximation to the size of such matchings - this algorithm runs in linear time for unit disks, and O(n log n) for general disks (as long as the density is relatively small).

Cite as

Sariel Har-Peled and Everett Yang. Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SoCG.2022.47,
  author =	{Har-Peled, Sariel and Yang, Everett},
  title =	{{Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.47},
  URN =		{urn:nbn:de:0030-drops-160555},
  doi =		{10.4230/LIPIcs.SoCG.2022.47},
  annote =	{Keywords: Matchings, disk intersection graphs, approximation algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail